//给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。 
//
// 示例 1: 
//
// 输入:
//[
// [ 1, 2, 3 ],
// [ 4, 5, 6 ],
// [ 7, 8, 9 ]
//]
//输出: [1,2,3,6,9,8,7,4,5]
// 
//
// 示例 2: 
//
// 输入:
//[
//  [1, 2, 3, 4],
//  [5, 6, 7, 8],
//  [9,10,11,12]
//]
//输出: [1,2,3,4,8,12,11,10,9,5,6,7]
// 
// Related Topics 数组 
// 👍 471 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：螺旋矩阵
public class P54SpiralMatrix {

    /**
     *
     * 思路： 先遍历行的所有 → ，再遍历去除头尾的列 ↓ ，再遍历 行的所有 ← ，再遍历去除头尾的列 ↑ 。一共四次，判断数据够了 就退出循环
     *
     * 执行用时： 0 ms , 在所有 Java 提交中击败了 100.00% 的用户 内存消耗： 37.7 MB , 在所有 Java 提交中击败了 33.99% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> list = new ArrayList<>();
            if (matrix.length == 0) {
                return list;
            }

            int m = matrix.length;  // m行
            int n = matrix[0].length;   // n列
            int total = m * n;

            int yEnd = m - 1;
            int xEnd = n - 1;

            int xStart = 0;
            int yStart = 0;

            while (list.size() < total) {
                // →
                for (int j = xStart; j < xEnd + 1 && list.size() < total; j++) {
                    list.add(matrix[yStart][j]);
                }

                // ↓
                for (int j = yStart + 1; j < yEnd && list.size() < total; j++) {
                    list.add(matrix[j][xEnd]);
                }

                // ←
                for (int j = xEnd; j >= xStart && list.size() < total; j--) {
                    list.add(matrix[yEnd][j]);
                }

                // ↑
                for (int j = yEnd - 1; j > yStart && list.size() < total; j--) {
                    list.add(matrix[j][xStart]);
                }
                xStart++;
                xEnd--;
                yStart++;
                yEnd--;
            }

            return list;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1,2,3},{4,5,6},{7,8,9}};
        Solution solution = new P54SpiralMatrix().new Solution();
        List<Integer> list = solution.spiralOrder(matrix);
        // TO TEST
        System.out.println(list);
    }

}